package edu.lambdateacher.parser;

/*
 LambdaTeacher
 Copyright (C) 2000  Kim Mason
 Copyright (C) 2014  Vitalij Zadneprovskij

 This program is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 2
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.apache.log4j.Logger;

import edu.lambdateacher.expressions.Abstraction;
import edu.lambdateacher.expressions.Application;
import edu.lambdateacher.expressions.Binding;
import edu.lambdateacher.expressions.Expression;
import edu.lambdateacher.expressions.Numbers;
import edu.lambdateacher.expressions.NumericalOperator;
import edu.lambdateacher.expressions.NumericalOperatorType;
import edu.lambdateacher.expressions.Variable;

/**
 * The parser for the Lambda Calculus. Takes in a LambdaScanner, and spits out a
 * Parse Tree. This is a simple recursive descent parser.
 */
public class LambdaParser {

	private static final Logger log = Logger.getLogger(LambdaParser.class);

	private static final String ERROR_MESSAGE = "A \"let = <expr>\" or <expr> expected.\n";
	
	// this boolean is whether there has been a parseerror yet or not
	private boolean parseerror = false;

	// sets used for error recovery
	private Set<LambdaTokenType> stopset;
	private Set<LambdaTokenType> startparse;
	private Set<LambdaTokenType> firstterm;

	
	
	/*
	 * Constructor function
	 */
	public LambdaParser() {
		super(); // implicit
		// first, create sets required by the parser for it's test and skip
		// routines.
		// create the stopping set
		stopset = new HashSet<LambdaTokenType>();
		stopset.add(LambdaTokenType.EOF);
		stopset.add(LambdaTokenType.LET);
		stopset.add(LambdaTokenType.RPAREN);

		// create the first set of expr (without the let)
		firstterm = new HashSet<LambdaTokenType>();
		firstterm.add(LambdaTokenType.LAMBDA);
		firstterm.add(LambdaTokenType.IDENT);
		firstterm.add(LambdaTokenType.NUMBER);
		firstterm.add(LambdaTokenType.LPAREN);
		firstterm.add(LambdaTokenType.PLUS);
		firstterm.add(LambdaTokenType.MINUS);
		firstterm.add(LambdaTokenType.STAR);
		firstterm.add(LambdaTokenType.SLASH);

		// create the first set of expr (with the let)
		startparse = new HashSet<LambdaTokenType>();
		startparse = new HashSet<LambdaTokenType>(firstterm);
		startparse.add(LambdaTokenType.LET);

		log.debug("Initialization finished the class is: " + this.toString());
	}

	/**
	 * test_and_skip is used in the parser to check if the current lexeme is in
	 * the set s1. If it isn't, the parser skips over lexemes until a lexeme in
	 * the set s1 union s2 is found. If this happens, parseerror is set to true.
	 * 
	 * @throws ParseException
	 */
	private LambdaScanner testAndSkip(LambdaScanner lambdaScanner, Set<LambdaTokenType> startSet, Set<LambdaTokenType> stopSet, String errorMessage) throws ParseException {

		log.debug("Begin of the method test_and_skip s1 = " + startSet + " s2 = " + stopSet + " errormsg = " + errorMessage);

		LambdaToken lambdaToken = lambdaScanner.currentToken();
		LambdaTokenType lambdaTokenType = lambdaToken.getTokenType();

		log.debug("Current token type: " + lambdaTokenType);

		// if the current token isn't a member of s1
		if (startSet.contains(lambdaTokenType) == false) {
			if (parseerror == false) {
				String errorstring;

				// construct the error string
				errorstring = "Error - Line " + Integer.toString(lambdaToken.getLineNumber());
				errorstring = errorstring + ", Position " + Integer.toString(lambdaToken.getLinePosition()) + ".  ";
				errorstring = errorstring + errorMessage;

				log.error(errorstring);
				parseerror = true;

				throw new ParseException(errorstring);
			}
		}
		// now create the union of s1 and s2
		Set<LambdaTokenType> theunion = new HashSet<LambdaTokenType>(startSet);
		theunion.addAll(stopSet);

		while (!theunion.contains(lambdaTokenType)) {
			lambdaToken = lambdaScanner.next();
			lambdaTokenType = lambdaToken.getTokenType();
		}
		
		return lambdaScanner;
	}

	/**
	 * isCurrentTokenSameAsInputParameter() checks if the current token is the same as the input parameter. If
	 * it is, it moves onto the next token and returns true. Otherwise, it only
	 * returns false.
	 */
	private boolean isCurrentTokenSameAsInputParameter(LambdaScanner lambdaScanner, LambdaTokenType symboltype) {
		LambdaToken currentLambdaToken = lambdaScanner.currentToken();
		if (currentLambdaToken.getTokenType() == symboltype) {
			currentLambdaToken = lambdaScanner.next();
			return true;
		}
		return false;
	}

	/**
	 * the parse method takes in a scanner, and returns a parse tree (A subclass
	 * of Expression) In EBNF, Parse parses <ALLEXPR> ::= let <name> = <EXPR> |
	 * <EXPR>. Note that Parse can return null (no expression entered, or a
	 * parse error occured). Every sub-parser can return null from these
	 * conditions.
	 * 
	 * @throws ParseException
	 */
	public ParseResult parse(LambdaScanner lambdaScanner, Map<String, Expression> boundExpressionMap) throws ParseException{
		log.debug("Beginning of the Parse method. thescanner = " + lambdaScanner + " boundExpressionMap =  " + boundExpressionMap);

		// initialise
		parseerror = false;

		Expression currentExpression = null;

		lambdaScanner = testAndSkip(lambdaScanner,startparse, stopset, ERROR_MESSAGE);

		// Have we got a top level binding
		if (isCurrentTokenSameAsInputParameter(lambdaScanner,LambdaTokenType.LET) == true) {
			String name = null;
			Set<LambdaTokenType> firstSet = new HashSet<LambdaTokenType>(); // first
																			// set
			Set<LambdaTokenType> followSet = new HashSet<LambdaTokenType>(); // followset

			followSet = new HashSet<LambdaTokenType>(stopset);
			followSet.add(LambdaTokenType.EQUALS);
			followSet.addAll(firstterm);

			// Parse a top level binding
			firstSet.add(LambdaTokenType.IDENT);
			testAndSkip(lambdaScanner,firstSet, followSet, "Identifier expected.\n");
			LambdaToken tok = lambdaScanner.currentToken();

			isCurrentTokenSameAsInputParameter(lambdaScanner, LambdaTokenType.IDENT);

			name = tok.getIdentifierName();

			followSet.remove(LambdaTokenType.EQUALS);
			firstSet = new HashSet<LambdaTokenType>();
			firstSet.add(LambdaTokenType.EQUALS);
			testAndSkip(lambdaScanner, firstSet, followSet, "A '=' expected.\n");
			isCurrentTokenSameAsInputParameter(lambdaScanner, LambdaTokenType.EQUALS);
			Expression body = parseExpr(lambdaScanner, boundExpressionMap, stopset);

			boundExpressionMap.put(name, body);
			currentExpression = new Binding(name, body);

		} else {
			// Parse a regular expression
			currentExpression = parseExpr(lambdaScanner, boundExpressionMap, stopset);
		}

		testAndSkip(lambdaScanner, stopset, new HashSet<LambdaTokenType>(), "Expression terminated un-expectedly.\n");

		ParseResult parseResult = new ParseResult();
		parseResult.setParseTree(currentExpression);
		parseResult.setBoundExpressionMap(boundExpressionMap);
		
		return parseResult;
	}
	
	/**
	 * parseExpr takes in a list of bound_vars (bound in the enclosing
	 * expression), and and Environment (which specifies pre-defined lambda
	 * expressions), and parses a Lambda Expression. A lambda expression can be
	 * made up of terms or applications (a term applied to a term). The EBNF is
	 * <EXPR> ::= [<term>]+
	 * 
	 * @throws ParseException
	 */
	private Expression parseExpr(LambdaScanner lambdaScanner, Map<String, Expression> boundExpressionMap, Set<LambdaTokenType> followset) throws ParseException {
		// clone the list of bound variables. This is done because a sub-parser
		// might
		// add to the list of bound variables, and we don't want that to effect
		// later
		// sub-parsers
		List<String> boundVariables = new ArrayList<String>(boundExpressionMap.keySet());

		// create the follow set of term
		Set<LambdaTokenType> followterm = new HashSet<LambdaTokenType>(followset);
		followterm.addAll(firstterm);

		// Parse a term
		Expression expr = parseTerm(lambdaScanner, boundVariables, boundExpressionMap, followterm);

		// If the next symbol is a variable, plus symbol, minus symbol, slash,
		// star, number,
		// lambda, or left parenthesis then we have an application (left
		// associative)
		LambdaToken tok = lambdaScanner.currentToken();
		
		Set<LambdaTokenType> goOnTokenTypes = new HashSet<LambdaTokenType>();
		goOnTokenTypes.add(LambdaTokenType.IDENT);
		goOnTokenTypes.add(LambdaTokenType.LAMBDA);
		goOnTokenTypes.add(LambdaTokenType.LPAREN);
		goOnTokenTypes.add(LambdaTokenType.PLUS);
		goOnTokenTypes.add(LambdaTokenType.MINUS);
		goOnTokenTypes.add(LambdaTokenType.STAR);
		goOnTokenTypes.add(LambdaTokenType.SLASH);
		goOnTokenTypes.add(LambdaTokenType.NUMBER);
		
		while(goOnTokenTypes.contains(tok.getTokenType()))
		{
			// Parse another term
			Expression arg = parseTerm(lambdaScanner, boundVariables, boundExpressionMap, followterm);

			if ((expr == null) && (arg == null)) {
				expr = null;
			} else if ((expr == null) && (arg != null)) {
				expr = arg;
			} else if ((expr != null) && (arg == null)) {
				// leave expr alone
			} else // ((expr != null) && (arg != null))
			{
				// Create the application
				Application appl = new Application(expr, arg);

				expr = appl;
			}

			// Get the next symbol and loop
			tok = lambdaScanner.currentToken();
		}

		// Return the expression parsed
		return expr;
	}
	
	
	/**
	 * parseTerms parses terms. Terms can be Variables, Numbers, Abstractions,
	 * parenthesized expressions, or numerical operations.
	 * 
	 * @throws ParseException
	 */
	private Expression parseTerm(LambdaScanner lambdaScanner, List<String> inbound_vars, Map<String, Expression> boundExpressionMap, Set<LambdaTokenType> followset) throws ParseException {
		// Terms can be variables, lambda abstractions, or parenthesised
		// expressions
		// and numbers and numerical operators

		Expression toreturn = null;
		// clone the bound expressions, as we don't want outer expressions to
		// inherit
		// the inner bound variables
		List<String> boundVariables = new ArrayList<String>(inbound_vars);

		LambdaToken tok = lambdaScanner.currentToken();

		testAndSkip(lambdaScanner, firstterm, followset, "A term expected.\n");

		if (tok.getTokenType() == LambdaTokenType.IDENT) {
			toreturn = parseVariable(lambdaScanner, boundVariables, boundExpressionMap, followset);

		} else if (tok.getTokenType() == LambdaTokenType.LAMBDA) {
			toreturn = parseAbstraction(lambdaScanner, boundVariables, boundExpressionMap, followset);
		} else if (tok.getTokenType() == LambdaTokenType.LPAREN) {
			toreturn = parseParenthExpr(lambdaScanner, boundVariables, boundExpressionMap, followset);
		} else if ((tok.getTokenType() == LambdaTokenType.PLUS) || (tok.getTokenType() == LambdaTokenType.MINUS) || (tok.getTokenType() == LambdaTokenType.STAR)
				|| (tok.getTokenType() == LambdaTokenType.SLASH)) {
			toreturn = parseNumOp(lambdaScanner, boundVariables);
		} else if (tok.getTokenType() == LambdaTokenType.NUMBER) {
			toreturn = parseNumbers(lambdaScanner);
		}

		// Now keep skipping until we find a follow symbol of term.
		testAndSkip(lambdaScanner, followset, new HashSet(), "Term terminated un-expectedly.\n");

		return toreturn;
	}

	
	/**
	 * parseVariable simply parses a variable and returns it.
	 */
	private Expression parseVariable(LambdaScanner lambdaScanner, List<String> inboundVariables, Map<String, Expression> boundExpressionMap, Set<LambdaTokenType> followset) {
		LambdaToken tok = lambdaScanner.currentToken();

		isCurrentTokenSameAsInputParameter(lambdaScanner, LambdaTokenType.IDENT);

		// first look up the variable in the list of bound variables
		//Enumeration<String> allelements = inbound_vars.elements();
		//String tempstr = null;
		Expression expression = null;

		// first, look in the list of bound_variable for the variable name
		for (String tempstr : inboundVariables) {
			if (tempstr.equals(tok.getIdentifierName())) {
				// Build up the variable expression
				expression = new Variable(tok.getIdentifierName());
				return expression;
			}
		}

		// If the variable isn't in the list of bound variables, look in the
		// Environment
		if (boundExpressionMap != null) {
			expression = boundExpressionMap.get(tok.getIdentifierName());
			if (expression != null)
				expression = (Expression) expression.clone();
		}
		if (expression != null) { // we found the variable in the environment, now
							// copy it
			Expression toreturn = null;

			toreturn = (Expression) expression.clone();

			return toreturn;
		}
		// Otherwise, the variable is un-bound, but that is allowed
		// Build up the variable expression
		expression = new Variable(tok.getIdentifierName());
		return expression;
	}
	
	
	private Expression parseAbstraction(LambdaScanner lambdaScanner, List<String> inboundVariables, Map<String, Expression> boundExpressionMap, Set<LambdaTokenType> followset) throws ParseException {
		List<String> bound_vars = new ArrayList<String>(inboundVariables);

		isCurrentTokenSameAsInputParameter(lambdaScanner, LambdaTokenType.LAMBDA);

		Set<LambdaTokenType> aset = new HashSet<LambdaTokenType>();
		Set<LambdaTokenType> fset = new HashSet<LambdaTokenType>(followset);
		aset.add(LambdaTokenType.IDENT);
		fset.add(LambdaTokenType.PERIOD);

		// Parse a lambda abstraction
		LambdaToken tok = lambdaScanner.currentToken();
		String bound_var = tok.getIdentifierName();

		testAndSkip(lambdaScanner, aset, fset, "An Identifier expected.\n");
		isCurrentTokenSameAsInputParameter(lambdaScanner, LambdaTokenType.IDENT);

		Abstraction abstr = null;
		Abstraction expr = null;

		// If we didn't have an IDENT, bound_var might be null
		if (bound_var != null) {
			// Add the bound variable to the bound_vars vector
			bound_vars.add(bound_var);
			abstr = new Abstraction(bound_var);
			expr = abstr;
		} else {
			parseerror = true;
			// something has gone wrong, so just try and take in the next ident
			tok = lambdaScanner.currentToken();
			if (isCurrentTokenSameAsInputParameter(lambdaScanner, LambdaTokenType.IDENT)) {
				bound_var = tok.getIdentifierName();
				bound_vars.add(bound_var);
				Abstraction tempabs = new Abstraction(bound_var);
				expr = tempabs;
				abstr = tempabs;
				expr = abstr;
			}
		}

		// keep trying to take in identifiers
		tok = lambdaScanner.currentToken();
		while (isCurrentTokenSameAsInputParameter(lambdaScanner, LambdaTokenType.IDENT)) {
			bound_var = tok.getIdentifierName();
			bound_vars.add(bound_var);
			Abstraction tempabs = new Abstraction(bound_var);
			abstr.setBody(tempabs);
			abstr = tempabs;
			tok = lambdaScanner.currentToken();
		}

		aset = new HashSet<LambdaTokenType>();
		aset.add(LambdaTokenType.PERIOD);
		fset.remove(LambdaTokenType.PERIOD);
		fset.addAll(firstterm);
		testAndSkip(lambdaScanner, aset, fset, "A '.' expected.\n");
		isCurrentTokenSameAsInputParameter(lambdaScanner, LambdaTokenType.PERIOD);
		Expression exprbody = parseExpr(lambdaScanner, boundExpressionMap, followset);
		// Build up a lambda abstraction expression
		if (abstr != null) {
			abstr.setBody(exprbody);
		}

		if (parseerror == true) {
			expr = null;
		}
		return expr;
	}
	
	private Expression parseParenthExpr(LambdaScanner lambdaScanner,List<String> inboundVariables, Map<String, Expression> boundExpressionMap, Set<LambdaTokenType> followset) throws ParseException {
		Set<LambdaTokenType> aset = new HashSet<LambdaTokenType>();
		Set<LambdaTokenType> fset = new HashSet<LambdaTokenType>(followset);
		fset.add(LambdaTokenType.RPAREN);

		isCurrentTokenSameAsInputParameter(lambdaScanner, LambdaTokenType.LPAREN);
		// Parse a parenthesised expression
		Expression expr = parseExpr(lambdaScanner, boundExpressionMap, followset);

		aset.add(LambdaTokenType.RPAREN);
		testAndSkip(lambdaScanner, aset, followset, "A ')' expected.\n");
		isCurrentTokenSameAsInputParameter(lambdaScanner, LambdaTokenType.RPAREN);
		return expr;
	}

	private Expression parseNumOp(LambdaScanner lambdaScanner,List<String> inboundVariables) {
		NumericalOperatorType operatortype = null;

		if (isCurrentTokenSameAsInputParameter(lambdaScanner, LambdaTokenType.PLUS)) {
			operatortype = NumericalOperatorType.PLUS;
		} else if (isCurrentTokenSameAsInputParameter(lambdaScanner, LambdaTokenType.MINUS)) {
			operatortype = NumericalOperatorType.MINUS;
		} else if (isCurrentTokenSameAsInputParameter(lambdaScanner, LambdaTokenType.STAR)) {
			operatortype = NumericalOperatorType.MULT;
		} else if (isCurrentTokenSameAsInputParameter(lambdaScanner, LambdaTokenType.SLASH)) {
			operatortype = NumericalOperatorType.DIV;
		}

		NumericalOperator numop = new NumericalOperator(operatortype);

		return numop;
	}

	private Expression parseNumbers(LambdaScanner lambdaScanner) {
		LambdaToken tok = lambdaScanner.currentToken();
		isCurrentTokenSameAsInputParameter(lambdaScanner, LambdaTokenType.NUMBER);
		Numbers toreturn = new Numbers(tok.getNumValue());
		return toreturn;
	}

	@Override
	public String toString() {
		return "LambdaParser [parseerror=" + parseerror + ", stopset=" + stopset + ", startparse=" + startparse + ", firstterm=" + firstterm + "]";
	}
}
